package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2019-12-29 20:27
 */
public class Q744 {
    public char nextGreatestLetter(char[] letters, char target) {
        int len = letters.length;
        if (target > letters[len - 1]) {
            return letters[0];
        }

        int start = 0, end = len - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (letters[mid] < target) {
                start = mid + 1;
            } else if (letters[mid] > target) {
                end = mid - 1;
            } else {
                start = mid;
            }
        }

        if(letters[end] <= target) {
            return letters[(end + 1) % len];
        }
        return letters[end];
    }

    public static void main(String[] args) {
        System.out.println(new Q744().nextGreatestLetter(new char[]{'e', 'e', 'e', 'e', 'e', 'e', 'n', 'n', 'n', 'n'}, 'e'));
    }
}
